|
In number theory, zero-sum problems are a certain class of combinatorial questions. In general, a finite abelian group ''G'' is considered. The zero-sum problem for the integer ''n'' is the following: Find the smallest integer ''k'' such that every sequence of elements of ''G'' with length contains ''n'' terms that sum to 0. In 1961 Paul Erdős, Abraham Ginzburg, and Abraham Ziv proved the general result for (the integers mod n) that : Explicitly this says that any multiset of 2''n'' − 1 integers has a subset of size ''n'' the sum of whose elements is a multiple of ''n''. This result is known as the Erdős–Ginzburg–Ziv theorem after its discoverers: it may be deduced from the Cauchy–Davenport theorem.〔Nathanson (1996) p.48〕 More general results than this theorem exist, such as Olson's theorem, Kemnitz's conjecture (proved by Christian Reiher in 2003〔.〕), and the weighted EGZ theorem (proved by David J. Grynkiewicz in 2005〔.〕). ==See also== * Davenport constant * Subset sum problem 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Zero-sum problem」の詳細全文を読む スポンサード リンク
|